package com.huawei.su;

import java.util.Stack;

/**
 * https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=654&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany
 */
public class BM2 {


    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        BM2 bm2 = new BM2();
        bm2.reverseBetween(listNode1, 1, 1);
    }

    private ListNode reverse(ListNode head, ListNode subEndAfter) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        while (true) {
            if (head.next == null) {
                stack.push(head);
                break;
            }
            stack.push(head);
            head = head.next;
        }
        ListNode newHead = stack.pop();
        ListNode index = head;

        while (true) {
            if (stack.isEmpty()) {
                index.next = subEndAfter;
                break;
            }
            index.next = stack.pop();
            index = index.next;
        }
        return newHead;
    }

    /**
     * @param head 链表信息
     * @param m    开始节点
     * @param n    终止节点
     * @return 部分反转后的新链表
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n) {
            return head;
        }
        // write code here
        int index = 0;
        ListNode subHead = null;
        ListNode subHeadAhead = null;
        ListNode subEnd = null;
        ListNode subEndAfter = null;
        ListNode temp = head;

        while (true) {
            index++;
            if (index > n) {
                break;
            }
            if (m > 1 && index == m - 1) {
                subHeadAhead = temp;
            }
            if (index == m) {
                subHead = temp;
            }
            if (index == n) {
                subEnd = temp;
                subEndAfter = subEnd.next;
                subEnd.next = null;
            }

            temp = temp.next;
        }
        ListNode subReverse = reverse(subHead, subEndAfter);
        if (subHeadAhead != null) {
            subHeadAhead.next = subReverse;
        }
        if (m > 1) {
            return head;
        } else {
            return subReverse;
        }
    }
}
